Baraj pentru lotul olimpic, Bucuresti, mai 1997
Problema 2: Cioplirea numerelor (Marius Popescu)
Dificultate: C4

Se da un numar de N cifre (o secventa de N cifre zecimale, in care prima
nu trebuie sa fie neaparat diferita de zero) cu N < 1000.
a) Sa se elimine K subsecvente disjuncte de cate L cifre consecutive
astfel incat secventa ramasa sa reprezinte numarul cel mai mare care
se poate forma in acest mod (K >= 0, L >= 0, K * L < N). Numarul poate
sa inceapa cu cifra zero.
b) Aceeasi problema, inlocuind "cel mai mare" cu "cel mai mic".

Intrare:
Fisierul de intrare contine zero sau mai multe seturi de date. Fiecare
set de date este format din doua linii. Prima linie contine numerele
N, K si L, in aceasta ordine, separate prin spatii; a doua linie contine
cele N cifre ale numarului, fara spatii.

Iesire:
Pentru fiecare set de date fisierul de iesire trebuie sa contina patru
linii. Prima linie trebuie sa contina pozitiile cifrelor din numarul dat
cu care incep subsecventele care trebuie sterse, in ordine crescatoare,
doua pozitii consecutive fiind separate de exact un spatiu. Pozitiile
cifrelor din numar sunt numerotate de la stanga la dreapta, in ordine
crescatoare, din unu in unu, incepand cu 1. A doua linie va contine
numarul obtinut prin eliminarea subsecventelor descrise pe prima linie
si care trebuie sa fie cel mai mare astfel de numar. Analog, liniile
trei si patru contin raspunsul la punctul (b).

Exemplu:
Intrare:
-------------------------------------------------------
20 2 3
12122212212212121222
10 3 3
0739276145
-------------------------------------------------------

Iesire:
-------------------------------------------------------
1 13
22212212221222
4 8
12112212121222
1 5 8
9
2 5 8
0
-------------------------------------------------------
==============================================
Solutie (Marius Popescu)
var
   f, g: text;
   n, k, l: integer;
   i, j, nn, s: integer;
   a: array [1..1000] of char;
   b: array [1..1000] of integer;
   tag: array [1..1000] of boolean;

begin
assign(f, 'p2.in');
reset(f);
assign(g, 'p2.out');
rewrite(g);
while not seekeof(f) do
   begin
   readln(f, n, k, l);
   for i := 1 to n do
      read(f, a[i]);
   readln(f);

   for i := 1 to n do
      begin
      b[i] := i;
      tag[i] := false;
      end;
   nn := n;
   a[n + 1] := 'Z';
   b[n + 1] := n + 1;
   for s := 1 to k do
      begin
      i := 1;
      while a[b[i]] >= a[b[i + l]] do
         i := i + 1;
      for j := i to i + l - 1 do
         tag[b[j]] := true;
      nn := nn - l;
      for j := i to nn + 1 do
         b[j] := b[j + l];
      end;
   i := 1;
   for s := 1 to k do
      begin
      while not tag[i] do
         i := i + 1;
      write(g, i);
      if s < k then
         write(g, ' ');
      i := i + l;
      end;
   writeln(g);
   for i := 1 to nn do
      write(g, a[b[i]]);
   writeln(g);

   for i := 1 to n do
      begin
      b[i] := i;
      tag[i] := false;
      end;
   nn := n;
   a[n + 1] := '!';
   b[n + 1] := n + 1;
   for s := 1 to k do
      begin
      i := 1;
      while a[b[i]] <= a[b[i + l]] do
         i := i + 1;
      for j := i to i + l - 1 do
         tag[b[j]] := true;
      nn := nn - l;
      for j := i to nn + 1 do
         b[j] := b[j + l];
      end;
   i := 1;
   for s := 1 to k do
      begin
      while not tag[i] do
         i := i + 1;
      write(g, i);
      if s < k then
         write(g, ' ');
      i := i + l;
      end;
   writeln(g);
   for i := 1 to nn do
      write(g, a[b[i]]);
   writeln(g);

   end;

close(f);
close(g);
end.
==================================
	TESTE
Intrare:
test 1:
20 2 3
12122212212212121222
--------------------------------
test 2:
10 3 3
0739286145
---------------------------------
test 3:
10 3 3
0793286145
----------------------------------
test 4:
99 10 4
784375437858913454312858974857388265784632578243564782365478657826524325783456827346578942365782346
---------------------------------
test 5:
99 30 3
784375437858913454312858974857388265784632578243564782365478657826524325783456827346578942365782346
---------------------------------
test 6:
99 80 1
784375437858913454312858974857388265784632578243564782365478657826524325783456827346578942365782346
----------------------------------
test 7:
800 1 500
01894375436178561043701603740865713050143567043372423847038216547383416473280463081634780546357804365437856104708167083264132708423463021473106435780654378014631027882046327804637854365837456374856783140573802412847321894732894712938743764654785896759687567345864573453278463248975893475489564356834876238745234623546493244503214632408372164078321657834056378562345789643759634176234782364623891463241647832146123682316666746578347693274161237849632179845312789451326954324543619632794632784968957645789634578962345789658765986759867567865786579086578805697805697805697850967856754768675347598734598347589734589743589347589345789435734897583495735978250723750275027527590175719832478931248702374298074382974128974128934712980478907654896754665615614613204001010430146186547856346146510043753456438651
----------------------------------
test 8:
800 10 50
01894375436178561043701603740865713050143567043372423847038216547383416473280463081634780546357804365437856104708167083264132708423463021473106435780654378014631027882046327804637854365837456374856783140573802412847321894732894712938743764654785896759687567345864573453278463248975893475489564356834876238745234623546493244503214632408372164078321657834056378562345789643759634176234782364623891463241647832146123682316666746578347693274161237849632179845312789451326954324543619632794632784968957645789634578962345789658765986759867567865786579086578805697805697805697850967856754768675347598734598347589734589743589347589345789435734897583495735978250723750275027527590175719832478931248702374298074382974128974128934712980478907654896754665615614613204001010430146186547856346146510043753456438651
----------------------------------
test 9:
800 50 10
01894375436178561043701603740865713050143567043372423847038216547383416473280463081634780546357804365437856104708167083264132708423463021473106435780654378014631027882046327804637854365837456374856783140573802412847321894732894712938743764654785896759687567345864573453278463248975893475489564356834876238745234623546493244503214632408372164078321657834056378562345789643759634176234782364623891463241647832146123682316666746578347693274161237849632179845312789451326954324543619632794632784968957645789634578962345789658765986759867567865786579086578805697805697805697850967856754768675347598734598347589734589743589347589345789435734897583495735978250723750275027527590175719832478931248702374298074382974128974128934712980478907654896754665615614613204001010430146186547856346146510043753456438651
----------------------------------
test 10:
800 500 1
01894375436178561043701603740865713050143567043372423847038216547383416473280463081634780546357804365437856104708167083264132708423463021473106435780654378014631027882046327804637854365837456374856783140573802412847321894732894712938743764654785896759687567345864573453278463248975893475489564356834876238745234623546493244503214632408372164078321657834056378562345789643759634176234782364623891463241647832146123682316666746578347693274161237849632179845312789451326954324543619632794632784968957645789634578962345789658765986759867567865786579086578805697805697805697850967856754768675347598734598347589734589743589347589345789435734897583495735978250723750275027527590175719832478931248702374298074382974128974128934712980478907654896754665615614613204001010430146186547856346146510043753456438651
=======================================

Iesire:
test 1:
22212212221222
12112212121222
--------------------------
test 2:
9
0
---------------------------
test 3:
6
0
-----------------------------
test 4:
98678243564782365478657826524325783456827346578942365782346
22463243564782365478657826524325783456827346578942365782346
-----------------------------
test 5:
988982346
222362346
-----------------------------
test 6:
9988888942365782346
1122222222223572346
------------------------------
test 7:
789634578962345789658765986759867567865786579086578805697805697805697850967856754768675347598734598347589734589743589347589345789435734897583495735978250723750275027527590175719832478931248702374298074382974128974128934712980478907654896754665615614613204001010430146186547856346146510043753456438651
018634578962345789658765986759867567865786579086578805697805697805697850967856754768675347598734598347589734589743589347589345789435734897583495735978250723750275027527590175719832478931248702374298074382974128974128934712980478907654896754665615614613204001010430146186547856346146510043753456438651
------------------------------
test 8:
999634578962345789658765986759867567865786579086578805697805697805697850967856754768675347598734598347589734589743589347589345789435734897583495735978250723750275027527590175719832478931248702374298074382974128974128934712980478907654896754665615614613204001010430146186547856346146510043753456438651
010034578962345789658765986759867567865786579086578805697805697805697850967856754768675347598734598347589734589743589347589345789435734897583495735978250723750275027527590175719832478931248702374298074382974128974128934712980478907654896754665615614613204001010430146186547856346146510043753456438651
-------------------------------
test 9:
999634578962345789658765986759867567865786579086578805697805697805697850967856754768675347598734598347589734589743589347589345789435734897583495735978250723750275027527590175719832478931248702374298074382974128974128934712980478907654896754665615614613204001010430146186547856346146510043753456438651
000012114562345789658765986759867567865786579086578805697805697805697850967856754768675347598734598347589734589743589347589345789435734897583495735978250723750275027527590175719832478931248702374298074382974128974128934712980478907654896754665615614613204001010430146186547856346146510043753456438651
-------------------------------
test 10:
999999999999999999999999998759867567865786579086578805697805697805697850967856754768675347598734598347589734589743589347589345789435734897583495735978250723750275027527590175719832478931248702374298074382974128974128934712980478907654896754665615614613204001010430146186547856346146510043753456438651
000000000000000000000000000000111111111111222086578805697805697805697850967856754768675347598734598347589734589743589347589345789435734897583495735978250723750275027527590175719832478931248702374298074382974128974128934712980478907654896754665615614613204001010430146186547856346146510043753456438651
================================

